package com.ljy.my_study.leetcode.重排链表;

import com.ljy.my_study.util.ListNodeUtil;
import com.ljy.my_study.util.ListNodeUtil.*;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author lijunying
 * @date 2021/11/22 10:59
 */
public class TestMain {

//    给定一个单链表 L 的头节点 head ，单链表 L 表示为：
//
//    L0 → L1 → … → Ln - 1 → Ln
//    请将其重新排列后变为：
//
//    L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
//    不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
//
//             
//
//    示例 1：
//
//
//
//    输入：head = [1,2,3,4]
//    输出：[1,4,2,3]
//    示例 2：
//
//
//
//    输入：head = [1,2,3,4,5]
//    输出：[1,5,2,4,3]
//             
//
//    提示：
//
//    链表的长度范围为 [1, 5 * 104]
//            1 <= node.val <= 1000
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/reorder-list
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        ListNode head=ListNodeUtil.createListNode(new int[]{1,2,3});
        new TestMain().reorderList(head);
        System.out.println(head);
    }

    public void reorderList(ListNode head) {
        if(head==null){
            return;
        }
        Deque<ListNode> deque=new LinkedList<>();
        int count=0;
        ListNode node=head;
        while(node!=null){
            deque.addLast(node);
            node=node.next;
            count++;
        }
        int mid=count/2;
        int num=0;
        node=head;
        while(num<mid){
            ListNode nextNext=node.next;
            ListNode next=deque.pollLast();
            next.next=nextNext;
            node.next=next;
            node=nextNext;
            num++;
        }
        node.next=null;
    }
}
